// const mergeSort = (nums) => {
//     if(nums.length <= 1) return nums
//     let mid = Math.floor(nums.length / 2)
//     ,left = nums.slice(0, mid)
//     ,right = nums.slice(mid)
//     return merge(mergeSort(left),mergeSort(right))
// }
// const merge = (left ,right) => {
//     let res = []
//     while(left.length > 0 && right.length > 0) {
//         if(left[0] < right[0]) {
//             res.push(left.shift())
//         }
//         else {
//             res.push(right.shift())
//         }
//     }
//     return res.concat(left).concat(right)
// }
// console.log(mergeSort([2,3,1,4,5,6,1,4]));

const mergeSort = (arr) => {
    if(arr.length < 2) return arr
    let mid = Math.floor(arr.length / 2)
    // 拆分为两个数组
    let left = arr.slice(0, mid),right = arr.slice(mid)
    return merge(mergeSort(left), mergeSort(right))
}

const merge = (left, right) => {
    let result = []
    while(left.length && right.length) {
        // 保证稳定
        if(left[0] <= right[0]) {
            result.push(left.shift())
        }
        else {
            result.push(right.shift())
        }
    }
    while(left.length) result.push(left.shift())
    while(right.length) result.push(right.shift())

    return result
}
let time = new Date().getTime()
console.log(mergeSort([2,3,1,4,5,6,1,4,1,2,3,56,12,21123,121,122,124,1,2,45,14,22,44,1,2,4,6,3,56,35,5]));
console.log(new Date().getTime() - time);